package com.study.lu.动态规划;

public class 最大子数组和 {
    /**
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 子数组 是数组中的一个连续部分。
     * <p>
     * 示例 1：
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
     * <p>
     * 示例 2：
     * 输入：nums = [1]
     * 输出：1
     * <p>
     * 示例 3：
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-subarray
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray2(nums));
    }

    /**
     * 贪心算法解。
     * <p>
     * eg：5,4,-1,7,8
     * 1.先取两个坐标  left=0, right=1;设置一个最大合计值 maxSum 首先maxSum = nums[left];
     * 2.如果maxSum+nums[right]>=0 则说明是可以连续新增的。那么right++ 进入循环
     * 3.如果maxSum+nums[right]<0 则说明已经碰到一个相对小值了。那么left++；sum归0，进入循环。
     *
     * @param nums
     * @return
     */
    private static int maxSubArray2(int[] nums) {
        int curSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            //
            curSum += nums[i];
            maxSum = Math.max(curSum, maxSum);
            // eg 1 2 3 -1 5 -10 x y z
            // 当到-10的时候，前面累加起来已经是负数了，对求和都没有贡献了。
            if (curSum < 0) {
                curSum = 0;
            }
        }

        return maxSum;
    }

    /**
     * 动态规划解。
     * <p>
     * 由题可得 请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 那么 dp(n) = max(nums(n),dp(n-1)+nums(n));
     * eg:数组nums[n] (1 -2 1 3 -1 4)
     * dp0 = 1
     * dp1 = max(dp0+(-2),-2) = -1 这里取得值包含坐标0的值。
     * dp2 = max(dp1+1,1) = 1  这里取得值包含坐标1的值。
     * dp3 = max(dp2+3,3) = 4  这里取得值包含坐标2的值。
     * dp4 = max(dp3+(-1),-1) = 3 这里取得值包含坐标3的值。
     * dp5 = max(dp4+4,4) = 7 这里取得值包含坐标4的值。
     * ......
     * 所以 dp(n-1)+nums[n] 没毛病.
     * 很明显 dp[n] 不是一定代表nums[n]的子数组之和最大值，而是包含nums[n]的子数组之和最大值。
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int length = nums.length;
        int dpsn_1 = nums[0];
        int dpsn;
        int max = dpsn_1;
        for (int i = 1; i < length; i++) {
            dpsn = Math.max(dpsn_1 + nums[i], nums[i]);
            max = Math.max(dpsn, max);
            dpsn_1 = dpsn;
        }
        return max;
    }
}
